package com.likeycy.my.sort;

import com.likeycy.my.sort.cmp.Sort;

/**
 * @ClassName: CountingSort
 * @Description: 计数排序：**仅对一定范围内的整数排序有效**
 * @Author: sodagreen
 * @Date: 2021/4/3 11:10
 * @Version: 1.0
 */
public class CountingSort extends Sort<Integer> {

    /**
     * 优化后的基数排序
     */
    @Override
    protected void sort() {
        // 找出最大值
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }

        // 开辟内存空间，存储次数
        int[] counts = new int[1 + (max - min)];
        // 统计每个整数出现的次数
        for (int i = 0; i < array.length; i++) {
            counts[array[i] - min]++;
        }

        // 累加次数。累加后的次数减去min数值就是该数字在数组中所在的索引区间范围
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

        // 从后往前遍历元素，将它放到有序数组的对应索引区间范围内
        int[] newArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            // newArray[--counts[array[i] - min]]：为了不复杂化能看懂，拆解开该语句
            int index = array[i] - min;
            int num = --counts[index];
            newArray[num] = array[i];
        }

        // 将已排好序的有序数组赋值给 array
        for (int i = 0; i < newArray.length; i++) {
            array[i] = newArray[i];
        }
    }

    /**
     * 未优化版本，存在以下问题：</p>
     * 1. 浪费内存空间 </p>
     * 2. 无法对负整数进行排序 </p>
     * 3. 不稳定 </p>
     */
    private void sort0() {
        // 找出最大值
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }

        // 开辟内存空间，存储每个整数出现的次数
        int[] counts = new int[1 + max];
        // 统计每个整数出现的次数
        for (int i = 0; i < array.length; i++) {
            /*int num = array[i];
            counts[num] += 1;*/
            // 简化上述两行代码。在指定元素的索引位置递增值
            counts[array[i]]++;
        }

        // 根据整数出现次数，对整数进行排序
        int index = 0;
        for (int i = 0; i < counts.length; i++) {
            while (counts[i] > 0) {
                array[index++] = i;
                counts[i]--;
            }
        }
    }
}
